package sort;

import java.util.Arrays;

/**
 * 归并排序
 * 分治法 <br />
 * 先把数组分开排序，然后再合并 <br />
 * 与数组的初始状态无关, 时间复杂度恒定 O(n * logn) <br />
 * 稳定
 *
 * @author yzh
 * @version 1.0
 * @date 2021/5/21 22:13
 */
public class MergeSort {
    public static void main(String[] args) {
        // 4, 1, 3, 9, 6, 8
        int[] nums = new int[]{4, 1, -9, 3, 9, 6, -8};
        new MergeSort().divideMerge(nums);
        System.out.println(Arrays.toString(nums));
    }

    int[] tmpArr, nums;

    public void divideMerge(int[] _nums) {
        nums = _nums;
        tmpArr = new int[nums.length];
        divide(0, nums.length - 1);
    }

    private void divide(int l, int r) {
        if (l >= r) return;
        int mid = l + (r - l) / 2;
        // 左子树
        divide(l, mid);
        // 右子树
        divide(mid + 1, r);
        merge(mid, l, r);
    }

    public void merge(int mid, int left, int right) {
        int i = left, j = mid + 1, k = 0;
        // 哪个小就先放入到 tmpArr 中, [left, mid] 和 [mid + 1, right] 之间的元素是有序的
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) tmpArr[k++] = nums[i++];
            else tmpArr[k++] = nums[j++];
        }
        while (i <= mid) tmpArr[k++] = nums[i++];
        while (j <= right) tmpArr[k++] = nums[j++];
        k = 0;
        int size = right - left + 1;
        while (k < size) nums[left++] = tmpArr[k++];
    }

    void mergeSortByIteration(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        for (int k = 1, i; k < n; k *= 2) {
            // 7 -> 3 + 4 -> (1 + 2) (2 + 2)
            i = 0;
            // 两两一组合并
            while (i + 2 * k - 1 < n) {
                merge(i, i + k - 1, i + 2 * k - 1);
                i += 2 * k;
            }
            // 0 1 2 3 4 5 6
            // 两两一组, 其中有一组的数量小于 k
            // 等于 nums.length - 1 会出现一次无效的排序
            if (i + k - 1 < n - 1) merge(i, i + k - 1, n - 1);
        }
    }

}
